{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Closest Prime Numbers in Range"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closestPrimes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #范围内最接近的两个质数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个正整数&nbsp;<code>left</code> 和&nbsp;<code>right</code>&nbsp;，请你找到两个整数&nbsp;<code>num1</code> 和&nbsp;<code>num2</code>&nbsp;，它们满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>left &lt;= nums1 &lt; nums2 &lt;= right&nbsp;</code>&nbsp;。</li>\n",
    "\t<li><code>nums1</code> 和&nbsp;<code>nums2</code>&nbsp;都是 <strong>质数</strong>&nbsp;。</li>\n",
    "\t<li><code>nums2 - nums1</code>&nbsp;是满足上述条件的质数对中的 <strong>最小值</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回正整数数组&nbsp;<code>ans = [nums1, nums2]</code>&nbsp;。如果有多个整数对满足上述条件，请你返回&nbsp;<code>nums1</code>&nbsp;最小的质数对。如果不存在符合题意的质数对，请你返回&nbsp;<code>[-1, -1]</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果一个整数大于&nbsp;<code>1</code>&nbsp;，且只能被&nbsp;<code>1</code> 和它自己整除，那么它是一个质数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>left = 10, right = 19\n",
    "<b>输出：</b>[11,13]\n",
    "<b>解释：</b>10 到 19 之间的质数为 11 ，13 ，17 和 19 。\n",
    "质数对的最小差值是 2 ，[11,13] 和 [17,19] 都可以得到最小差值。\n",
    "由于 11 比 17 小，我们返回第一个质数对。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>left = 4, right = 6\n",
    "<b>输出：</b>[-1,-1]\n",
    "<b>解释：</b>给定范围内只有一个质数，所以题目条件无法被满足。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= left &lt;= right &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [closest-prime-numbers-in-range](https://leetcode.cn/problems/closest-prime-numbers-in-range/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [closest-prime-numbers-in-range](https://leetcode.cn/problems/closest-prime-numbers-in-range/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10\\n19', '4\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        t = [-1, -1]\n",
    "        if left <= 2:\n",
    "            return [2, 3] if right >= 3 else t \n",
    "        for a, b in pairwise(filter(lambda x: all(x % i for i in range(3, isqrt(x) + 1, 2)), range(left | 1, right + 1, 2))):\n",
    "            c = b - a\n",
    "            if c == 2:\n",
    "                return [a, b]\n",
    "            if c < right:\n",
    "                right = c\n",
    "                t = [a, b]\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        \n",
    "        def primes(x):\n",
    "            if x == 2:\n",
    "                return True\n",
    "            \n",
    "            if x % 2 == 0:\n",
    "                return False\n",
    "\n",
    "            for i in range(3, int(pow(x, 0.5)) + 1, 2):\n",
    "                if x % i == 0 and x != i:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        # cands = [x for x in range(left, right+1) if x > 1 and primes(x)]\n",
    "        # return cands\n",
    "        \n",
    "        diff = float('inf')\n",
    "        \n",
    "        ans = [-1, -1]\n",
    "        \n",
    "        prev = -1 if left > 2 else 2\n",
    "        if right <= 2: return ans\n",
    "        \n",
    "        if left % 2 == 0: left += 1\n",
    "        for x in range(max(3, left), right+1, 2):\n",
    "            if primes(x):\n",
    "                if prev < 0: prev = x\n",
    "                else:\n",
    "                    tmp = x - prev\n",
    "                    if tmp < diff: \n",
    "                        diff = tmp\n",
    "                        ans = [prev, x]\n",
    "                    prev = x\n",
    "                    if diff <= 2: return ans\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        def is_prime(x):\n",
    "            if (x == 2) or (x == 3):\n",
    "                return True\n",
    "            if (x % 6 != 1) and (x % 6 != 5):\n",
    "                return False\n",
    "            for i in range(5, int(x ** 0.5) + 1, 6):\n",
    "                if (x % i == 0) or (x % (i + 2) == 0):\n",
    "                    return False\n",
    "            return True\n",
    "        ps = []\n",
    "        for i in range(left, right+1):\n",
    "            if i > 1 and is_prime(i):\n",
    "                ps.append(i)\n",
    "#         print(ps)\n",
    "        pre = inf\n",
    "        ans = [-1, -1]\n",
    "        for a, b in pairwise(ps):\n",
    "            if b - a < pre:\n",
    "                ans = [a, b]\n",
    "                pre = b - a\n",
    "#             print(a, b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_prime(self, x):\n",
    "        if x==1:\n",
    "            return False\n",
    "        if x==2 or x==3:\n",
    "            return True\n",
    "\n",
    "        if (x%6!=1) and (x%6!=5):\n",
    "            return False\n",
    "\n",
    "        for i in range(5, int(x**0.5)+1, 6):\n",
    "            if (x%i==0) or (x%(i+2)==0):\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        primes = []\n",
    "        for i in range(left, right+1):\n",
    "            if self.is_prime(i): primes.append(i)\n",
    "\n",
    "        length = len(primes)\n",
    "        if length <= 1:\n",
    "            return([-1,-1])\n",
    "        elif length == 2:\n",
    "            return(primes)\n",
    "        \n",
    "        left = right = Min = 0xfffffff\n",
    "        for index in range(1, len(primes)):\n",
    "            if(primes[index] - primes[index-1])<Min:\n",
    "                Min = primes[index] - primes[index-1]\n",
    "                left = primes[index-1]\n",
    "                right = primes[index]\n",
    "\n",
    "        return [left,right] \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "prime = []\n",
    "def isPrime(num):\n",
    "    if num == 1: return False\n",
    "    for i in range(2,int(num**0.5) + 1):\n",
    "        if num % i == 0:\n",
    "            return False\n",
    "    return True\n",
    "for i in range(1,10**6+4):\n",
    "    if isPrime(i):\n",
    "        prime.append(i)\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        i = bisect_left(prime,left)\n",
    "        j = bisect_right(prime,right)\n",
    "        if j - i == 1: return [-1,-1]\n",
    "        x,y,d = -1, -1, float(\"inf\")\n",
    "        for m in range(i+1,j):\n",
    "            if prime[m] - prime[m-1] < d:\n",
    "                x, y = prime[m-1], prime[m]\n",
    "                d = prime[m] - prime[m-1]\n",
    "            if d <= 2: return [x, y]\n",
    "        return [x, y]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "from bisect import bisect_left\n",
    " \n",
    "def isPrime(n):\n",
    "    if (n <= 1):\n",
    "        return False\n",
    "    for i in range(2, int(sqrt(n))+1):\n",
    "        if (n % i == 0):\n",
    "            return False\n",
    " \n",
    "    return True\n",
    "primes = [2, 3] + [i for i in range(5, 10 ** 6 + 1, 2) if isPrime(i)]\n",
    "#print(primes[-10:])\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        idx1 = bisect_left(primes, left)\n",
    "        # print(primes[idx1 + 1])\n",
    "        if idx1 == len(primes) or primes[idx1 + 1] > right:\n",
    "            return [-1, -1]\n",
    "        ret = [primes[idx1], primes[idx1 + 1]]\n",
    "        retval = primes[idx1 + 1] - primes[idx1]\n",
    "        for i in range(idx1, len(primes) - 1):\n",
    "            if primes[i + 1] > right:\n",
    "                break\n",
    "            t = primes[i + 1] - primes[i]\n",
    "            if t < retval:\n",
    "                retval = t\n",
    "                ret = [primes[i], primes[i + 1]]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        def check(a: int):\n",
    "            if a == 1:\n",
    "                return False\n",
    "            if (a == 2) or (a == 3):\n",
    "                return True\n",
    "            if (a % 6 != 1) and (a % 6 != 5):\n",
    "                return False\n",
    "            for i in range(5, int(a ** 0.5) + 1, 6):\n",
    "                if (a % i == 0) or (a % (i + 2) == 0):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        nums = []\n",
    "        res = [-1, -1]\n",
    "        mn = sys.maxsize\n",
    "        for i in range(left, right + 1, 1):\n",
    "            if check(i):\n",
    "                if len(nums):\n",
    "                    if i - nums[-1] < mn:\n",
    "                        mn = i - nums[-1]\n",
    "                        res = [nums[-1], i]\n",
    "                nums.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "BASE = []\n",
    "\n",
    "import random\n",
    "\n",
    "def is_prime(num, k=5):\n",
    "    if num <= 3:\n",
    "        return num == 2 or num == 3\n",
    "    if num % 2 == 0:\n",
    "        return False\n",
    "\n",
    "    # 将 num - 1 表示为 2^r * d 的形式\n",
    "    r, d = 0, num - 1\n",
    "    while d % 2 == 0:\n",
    "        r += 1\n",
    "        d //= 2\n",
    "\n",
    "    # 进行 k 轮测试\n",
    "    for i in range(k):\n",
    "        a = random.randint(2, num - 2)\n",
    "        x = pow(a, d, num)\n",
    "        if x == 1 or x == num - 1:\n",
    "            continue\n",
    "        for j in range(r - 1):\n",
    "            x = pow(x, 2, num)\n",
    "            if x == num - 1:\n",
    "                break\n",
    "        else:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "for i in range(2, 10 ** 6):\n",
    "    if is_prime(i):\n",
    "        BASE.append(i)\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        diff = inf\n",
    "        res = [-1, -1]\n",
    "        \n",
    "        pre = None\n",
    "        for n in BASE:\n",
    "            \n",
    "            if n > right:\n",
    "                break\n",
    "                \n",
    "            if pre is not None and pre >= left:\n",
    "                if n - pre < diff:\n",
    "                    diff = n - pre\n",
    "                    res = [pre, n]\n",
    "            \n",
    "            \n",
    "            \n",
    "            pre = n\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        # pointer = 6*(left//6)+5\n",
    "        def checkPrimes(x):\n",
    "            if (x == 2) or (x == 3):\n",
    "                return True\n",
    "            if (x % 6 != 1) and (x % 6 != 5):\n",
    "                return False\n",
    "            for i in range(5, int(x ** 0.5) + 1, 6):\n",
    "                if (x % i == 0) or (x % (i + 2) == 0):\n",
    "                    return False\n",
    "            return True\n",
    "        cnt = 0\n",
    "        f = 1\n",
    "        ans = []\n",
    "        pre = []\n",
    "        if 6*(left//6)+1>=left:\n",
    "            p = 6*(left//6)+1\n",
    "            while p<=right:\n",
    "                # print(p)\n",
    "                if f:\n",
    "                    if checkPrimes(p):\n",
    "                        pre.append(p)\n",
    "                        cnt += 1\n",
    "                        if cnt<=2:\n",
    "                            ans.append(p)\n",
    "                        if cnt>2 and ans[1]-ans[0]>p - pre[-2]:\n",
    "                            t = pre[-2]\n",
    "                            ans = [t, p]\n",
    "                    p += 4\n",
    "                    f = 1-f\n",
    "                else:\n",
    "                    if checkPrimes(p):\n",
    "                        pre.append(p)\n",
    "                        cnt += 1\n",
    "                        if cnt<=2:\n",
    "                            ans.append(p)\n",
    "                        if cnt>2 and ans[1]-ans[0]>p - pre[-2]:\n",
    "                            t = pre[-2]\n",
    "                            ans = [t, p]\n",
    "                    p += 2\n",
    "                    f = 1-f         \n",
    "        if 6*(left//6)+1<left:\n",
    "            p = 6*(left//6)+5\n",
    "            while p<=right:\n",
    "                if f:\n",
    "                    if checkPrimes(p):\n",
    "                        pre.append(p)\n",
    "                        cnt += 1\n",
    "                        if cnt<=2:\n",
    "                            ans.append(p)\n",
    "                        if cnt>2 and ans[1]-ans[0]>p - pre[-2]:\n",
    "                            t = pre[-2]\n",
    "                            ans = [t, p]\n",
    "                    p += 2\n",
    "                    f = 1-f\n",
    "                else:\n",
    "                    if checkPrimes(p):\n",
    "                        pre.append(p)\n",
    "                        cnt += 1\n",
    "                        if cnt<=2:\n",
    "                            ans.append(p)\n",
    "                        if cnt>2 and ans[1]-ans[0]>p - pre[-2]:\n",
    "                            t = pre[-2]\n",
    "                            ans = [t, p]\n",
    "                    p += 4\n",
    "                    f = 1-f\n",
    "        if len(ans)<2:\n",
    "            return[-1,-1]\n",
    "        if left == 1:\n",
    "            if right <= 2:\n",
    "                return[-1,-1]\n",
    "            if right >= 3:\n",
    "                return[2,3]\n",
    "        return ans      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        c = []\n",
    "        qx = list(map(int, \"2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997\".split(\" \")))\n",
    "        def helper(q):\n",
    "            for i in qx:\n",
    "                if i<q and q%i==0:\n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(max(left,2), right+1):\n",
    "            if helper(i):\n",
    "                c.append(i)\n",
    "        if len(c)<2:\n",
    "            return [-1, -1]\n",
    "        res = [-1, -1]\n",
    "        d = 10**6\n",
    "        for a,b in zip(c[:-1], c[1:]):\n",
    "            if b-a<d:\n",
    "                d = b-a\n",
    "                res = [a,b]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = []\r\n",
    "for i in range(2, 1000001):\r\n",
    "    isPrime = True\r\n",
    "    for j in range(2, int(i ** 0.5) + 1):\r\n",
    "        if i % j == 0:\r\n",
    "            isPrime = False\r\n",
    "            break\r\n",
    "    if isPrime:\r\n",
    "        primes.append(i)\r\n",
    "class Solution:\r\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\r\n",
    "        center = []\r\n",
    "        for i in range(len(primes)):\r\n",
    "            if  left <= primes[i] <= right:\r\n",
    "                center.append(primes[i])\r\n",
    "        if len(center) < 2:\r\n",
    "            return [-1, -1]\r\n",
    "        minDiff = float('inf')\r\n",
    "        for i in range(1, len(center)):\r\n",
    "            if center[i] - center[i - 1] < minDiff:\r\n",
    "                minDiff = center[i] - center[i - 1]\r\n",
    "                res = [center[i - 1], center[i]]\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000000\n",
    "\n",
    "#eratosthenes\n",
    "isPrime = bytearray([1]) * N\n",
    "isPrime[0] = isPrime[1] = 0\n",
    "for i in range(2, isqrt(N) + 1):\n",
    "    if isPrime[i]:\n",
    "        isPrime[i * i: N: i] = bytearray([0]) * ((N - 1) // i - i + 1)\n",
    "primes = [p for p in range(2, N) if isPrime[p]]\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, L: int, R: int) -> List[int]:\n",
    "        dif, res = N, [-1, -1]\n",
    "        for a, b in pairwise(primes[bisect_left(primes, L): bisect_right(primes, R)]):\n",
    "            if b - a < dif:\n",
    "                dif = b - a\n",
    "                res = [a, b]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def is_prime(x):\n",
    "    for i in range(2, int(x ** 0.5) + 1):\n",
    "        if x % i == 0: return False\n",
    "    return True\n",
    "\n",
    "primes = []\n",
    "for i in range(2, 10 ** 6 + 1):\n",
    "    if is_prime(i):\n",
    "        primes.append(i)\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        l, r = bisect_left(primes, left), bisect_right(primes, right)\n",
    "        print(primes[l:r])\n",
    "        best, ans = inf, [-1, -1]\n",
    "        for i in range(l + 1, r):\n",
    "            if primes[i] - primes[i - 1] < best:\n",
    "                ans = [primes[i - 1], primes[i]]\n",
    "                best = primes[i] - primes[i - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#generate all primes [1,10**6]\n",
    "#bisection to find all primes in between\n",
    "\n",
    "#or generate all primes between [l,r]\n",
    "#take diff between the consecutive primes and record the smallest diff and pair.\n",
    "primes=[]\n",
    "K=1000000\n",
    "for i in range(2,K+1):\n",
    "    flag=1\n",
    "    ub=int(i**0.5)+1\n",
    "    for d in range(2,min(ub,i)):\n",
    "        if i%d==0: \n",
    "            flag=0\n",
    "            break\n",
    "    if flag: primes.append(i)\n",
    "P=set(primes)\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def closestPrimes(self, l: int, r: int) -> List[int]:\n",
    "        i,j=bisect_left(primes,l),bisect_left(primes,r)\n",
    "        if r in P: j+=1\n",
    "        if j-i<1: return [-1,-1]\n",
    "        res=[-1,-1]\n",
    "        m=float('inf')\n",
    "        for k in range(i,j-1):\n",
    "            d=primes[k+1]-primes[k]\n",
    "            if d<m:\n",
    "                res=[primes[k],primes[k+1]]\n",
    "                m=d\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    d = {}\n",
    "    maxi = 0\n",
    "\n",
    "    def is_prime(self, num):\n",
    "        if num < self.maxi:\n",
    "            if num in self.d:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        if self.maxi < num:\n",
    "            self.maxi = num\n",
    "\n",
    "        if num == 1:\n",
    "            return False\n",
    "        for i in range(2, int(math.sqrt(num)) + 1):\n",
    "            if num % i == 0:\n",
    "                return False\n",
    "        \n",
    "        self.d[num] = 1\n",
    "        return True\n",
    "\n",
    "    # primes = []\n",
    "    def __init__(self):\n",
    "        if len(self.d) == 0:\n",
    "            for i in range(1, 1000000):\n",
    "                self.is_prime(i)\n",
    "        \n",
    "        \n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        maxd = 99999999\n",
    "        res = [-1,-1]\n",
    "        l = 0\n",
    "        r = 0\n",
    "        for i in range(left, right + 1):\n",
    "            if i in self.d:\n",
    "                # print(i, \"是质数\")\n",
    "                if l == 0:\n",
    "                    l = i\n",
    "                    # print(l, \"l被赋值\")\n",
    "                    continue\n",
    "                else:\n",
    "                    if r == 0:\n",
    "                        # print(l, \"r被赋值\")\n",
    "                        r = i\n",
    "                    else:\n",
    "                        l = r\n",
    "                        r = i\n",
    "                    # print(\"计算差值\",l , r)\n",
    "                    if maxd > r-l:\n",
    "                        maxd = r-l\n",
    "                        res = [l,r]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "import bisect\n",
    "\n",
    "MAX = 10 ** 6;\n",
    "\n",
    "PRIMES = [2];\n",
    "\n",
    "# Sieve of Sundaram\n",
    "def sieve():  \n",
    "    n_new = 10 ** 3\n",
    "    marked = [False] * (MAX // 2 + 500)\n",
    "    for i in range(1, n_new // 2 + 1):\n",
    "        for j in range(2 * i * (i + 1), MAX // 2 + 1, 2 * i + 1):\n",
    "            marked[j] = True\n",
    "    for i in range(1, MAX // 2 + 1):\n",
    "        if (marked[i] == 0):\n",
    "            PRIMES.append(2 * i + 1)\n",
    "\n",
    "sieve()\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        l = bisect.bisect_left(PRIMES, left)\n",
    "        diff = float(\"inf\")\n",
    "        res_ind = -1\n",
    "        for i in range(l, len(PRIMES) - 1):\n",
    "            if PRIMES[i + 1] > right:\n",
    "                break\n",
    "            new_diff = PRIMES[i + 1] - PRIMES[i]\n",
    "            if new_diff < diff:\n",
    "                diff = new_diff\n",
    "                res_ind = i\n",
    "\n",
    "        if res_ind == -1:\n",
    "            return [-1, -1]\n",
    "        return [PRIMES[res_ind], PRIMES[res_ind + 1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "al_primes= set()\n",
    "def is_prime4(x):\n",
    "    if (x == 2) or (x == 3):\n",
    "        return True\n",
    "    if (x % 6 != 1) and (x % 6 != 5):\n",
    "        return False\n",
    "    for i in range(5, int(x ** 0.5) + 1, 6):\n",
    "        if (x % i == 0) or (x % (i + 2) == 0):\n",
    "            return False\n",
    "    return True\n",
    "for i in range(2, 1000001):\n",
    "    if is_prime4(i):al_primes.add(i)\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        # 找到left-right之间的所有质数\n",
    "        al_k = []\n",
    "\n",
    "        for i in range(left, right + 1):\n",
    "            if i in al_primes:\n",
    "                al_k.append(i)\n",
    "        \n",
    "        if len(al_k) < 2:\n",
    "            return [-1, -1]\n",
    "        if al_k[0]==1:\n",
    "            al_k = al_k[1:]\n",
    "        t = float('inf')\n",
    "        ans = [-1, -1]\n",
    "        for i in range(1, len(al_k)):\n",
    "            if al_k[i] - al_k[i - 1] < t:\n",
    "                ans = [al_k[i - 1], al_k[i]]\n",
    "                t = al_k[i] - al_k[i - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "isprime = [True] * 1000005\n",
    "isprime[0] = False\n",
    "isprime[1] = False\n",
    "for i in range(2, 1000005):\n",
    "    if isprime[i]:\n",
    "        for j in range(2 * i, 1000005, i):\n",
    "            isprime[j] = False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        \n",
    "        \n",
    "        ans = [-100000000, 1000000]\n",
    "        la = -100000000 \n",
    "        for i in range(left, right + 1):\n",
    "            if isprime[i]:\n",
    "                if i - la < ans[1] - ans[0]:\n",
    "                    ans = [la, i]\n",
    "                la = i\n",
    "\n",
    "        if ans[0] < 0:\n",
    "            return [-1, -1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx = 10 ** 6 + 1\n",
    "f = [True] * mx\n",
    "for i in range(2, mx):\n",
    "    if f[i]:               \n",
    "        for j in range(i * i, mx, i):\n",
    "            f[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        ans1 = ans2 = None\n",
    "        nums1 = nums2 = None\n",
    "        for i in range(2, right + 1):\n",
    "            if f[i] and i >= left:\n",
    "                nums1, nums2 = nums2, i\n",
    "                if ans1 is None or ans2 is None:\n",
    "                    ans1, ans2 = nums1, nums2\n",
    "                elif ans2 - ans1 > nums2 - nums1:\n",
    "                    ans1, ans2 = nums1, nums2\n",
    "        return [ans1, ans2] if ans1 is not None and ans2 is not None else [-1, -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from array import array\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "from functools import lru_cache\n",
    "from math import floor, gcd\n",
    "from random import randint\n",
    "from typing import DefaultDict, List\n",
    "\n",
    "\n",
    "class EratosthenesSieve:\n",
    "    \"\"\"埃氏筛\"\"\"\n",
    "\n",
    "    __slots__ = \"_minPrime\"  # 每个数的最小质因数\n",
    "\n",
    "    def __init__(self, maxN: int):\n",
    "        \"\"\"预处理 O(nloglogn)\"\"\"\n",
    "        minPrime = array(\"I\", range(maxN + 1))\n",
    "        upper = int(maxN**0.5) + 1\n",
    "        for i in range(2, upper):\n",
    "            if minPrime[i] < i:\n",
    "                continue\n",
    "            for j in range(i * i, maxN + 1, i):\n",
    "                if minPrime[j] == j:\n",
    "                    minPrime[j] = i\n",
    "        self._minPrime = minPrime\n",
    "\n",
    "    def isPrime(self, n: int) -> bool:\n",
    "        if n < 2:\n",
    "            return False\n",
    "        return self._minPrime[n] == n\n",
    "\n",
    "    def getPrimeFactors(self, n: int) -> \"DefaultDict[int, int]\":\n",
    "        \"\"\"求n的质因数分解 O(logn)\"\"\"\n",
    "        res, f = defaultdict(int), self._minPrime\n",
    "        while n > 1:\n",
    "            m = f[n]\n",
    "            res[m] += 1\n",
    "            n //= m\n",
    "        return res\n",
    "\n",
    "    def getPrimes(self) -> List[int]:\n",
    "        return [x for i, x in enumerate(self._minPrime) if i >= 2 and i == x]\n",
    "\n",
    "\n",
    "# 给你两个正整数 left 和 right ，请你找到两个整数 num1 和 num2 ，它们满足：\n",
    "\n",
    "# left <= nums1 < nums2 <= right  。\n",
    "# nums1 和 nums2 都是 质数 。\n",
    "# nums2 - nums1 是满足上述条件的质数对中的 最小值 。\n",
    "# 请你返回正整数数组 ans = [nums1, nums2] 。如果有多个整数对满足上述条件，请你返回 nums1 最小的质数对。如果不存在符合题意的质数对，请你返回 [-1, -1] 。\n",
    "\n",
    "# 如果一个整数大于 1 ，且只能被 1 和它自己整除，那么它是一个质数。\n",
    "\n",
    "S = EratosthenesSieve(int(1e6 + 10))\n",
    "\n",
    "P = S.getPrimes()\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        ok = []\n",
    "        for p in P:\n",
    "            if left <= p <= right:\n",
    "                ok.append(p)\n",
    "        if len(ok) < 2:\n",
    "            return [-1, -1]\n",
    "        res = [ok[0], ok[1]]\n",
    "        for i in range(1, len(ok)):\n",
    "            if ok[i] - ok[i - 1] < res[1] - res[0]:\n",
    "                res = [ok[i - 1], ok[i]]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(i):\n",
    "    for j in range(2,int(sqrt(i)+1)):\n",
    "        if i%j==0:\n",
    "            return False\n",
    "    return True\n",
    "myset=set()\n",
    "myset.add(2)\n",
    "for i in range(3,1000000,2):\n",
    "    if check(i):\n",
    "        myset.add(i)\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        m=[]\n",
    "        minn=100000\n",
    "        ans=[-1,-1]\n",
    "        for i in range(left,right+1):\n",
    "            if i in myset:\n",
    "                m.append(i)\n",
    "                if len(m)>=2 and m[-1]-m[-2]<minn:\n",
    "                    minn=m[-1]-m[-2]\n",
    "                    ans=m[-2:]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10 ** 6 + 1\n",
    "primes = [True] * M\n",
    "for i in range(2, M):\n",
    "    if not primes[i]:\n",
    "        continue\n",
    "    for j in range(2 * i, M, i):\n",
    "        primes[j] = False\n",
    "primes[0] = False\n",
    "primes[1] = False\n",
    "        \n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        ans = inf\n",
    "        res = [-1, -1]\n",
    "        last = -1\n",
    "        # print(primes[:20])\n",
    "        for i in range(left, right + 1):\n",
    "            if primes[i]:\n",
    "                if last != -1:\n",
    "                    # print(i, primes[i])\n",
    "                    if ans > i - last:\n",
    "                        ans = i - last\n",
    "                        res = [last, i]\n",
    "                last = i\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        array = [True]*1000001\n",
    "        array[0]=array[1]=False\n",
    "        \n",
    "        for i in range(2, right+1):\n",
    "            if array[i]:\n",
    "                for j in range(i*2, right+1, i):\n",
    "                    array[j] = False \n",
    "        \n",
    "        diff = 1000001\n",
    "        res = [-1,-1]\n",
    "        leftNum = -1\n",
    "        for i in range(left, right+1):\n",
    "            if array[i]:\n",
    "                if leftNum!=-1 and i-leftNum<diff:\n",
    "                    diff=i-leftNum\n",
    "                    res = [leftNum,i]\n",
    "                leftNum = i\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 6 + 1\n",
    "primes = []\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "primes.extend((MX, MX))  # 保证下面下标不会越界\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        p = q = -1\n",
    "        i = bisect_left(primes, left)\n",
    "        while primes[i + 1] <= right:\n",
    "            if p < 0 or primes[i + 1] - primes[i] < q - p:\n",
    "                p, q = primes[i], primes[i + 1]\n",
    "            i += 1\n",
    "        return [p, q]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "MX =10**6+1\n",
    "pli = [1]*(MX+1)\n",
    "pli[0],pli[1] = 0,0\n",
    "for i in range(MX):\n",
    "    if pli[i] == 1:\n",
    "        n = 2\n",
    "        while i*n <= MX:\n",
    "            pli[i*n] = 0\n",
    "            n += 1\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        plis = []\n",
    "        for i in range(left,right+1):\n",
    "            if pli[i] == 1:\n",
    "                plis.append(i)\n",
    "        if len(plis) <= 1:\n",
    "            return [-1,-1]\n",
    "        min = right\n",
    "        for i in range(len(plis)-1):\n",
    "            if plis[i+1] - plis[i] < min:\n",
    "                num1 = plis[i]\n",
    "                num2 = plis[i+1]\n",
    "                min = plis[i+1] - plis[i]\n",
    "                if min == 2:\n",
    "                    break\n",
    "        return [num1,num2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(i):\n",
    "    for j in range(2,int(sqrt(i)+1)):\n",
    "        if i%j==0:\n",
    "            return False\n",
    "    return True\n",
    "myset=set()\n",
    "for i in range(2,1050000):\n",
    "    if check(i):\n",
    "        myset.add(i)\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        m=[]\n",
    "        minn=100000\n",
    "        ans=[-1,-1]\n",
    "        for i in range(left,right+1):\n",
    "            if i in myset:\n",
    "                m.append(i)\n",
    "                if len(m)>=2 and m[-1]-m[-2]<minn:\n",
    "                    minn=m[-1]-m[-2]\n",
    "                    ans=m[-2:]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def eratosthenes(n):\n",
    "    primes = []\n",
    "    is_prime = [True] * (n + 1)\n",
    "    for i in range(2, n+1):\n",
    "        if is_prime[i]:\n",
    "            primes.append(i)\n",
    "            # 用当前素数i去筛掉所有能被它整除的数\n",
    "            for j in range(i * 2, n+1, i):\n",
    "                is_prime[j] = False\n",
    "    return primes\n",
    "primes = eratosthenes(10 ** 6)\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        global primes\n",
    "        primes_ = primes[bisect_left(primes, left):bisect_right(primes, right)]\n",
    "        a = b = -1\n",
    "        min_ = inf\n",
    "        for c, d in zip(primes_[:-1], primes_[1:]):\n",
    "            if d - c < min_: a, b, min_ = c, d, d - c\n",
    "        \n",
    "        return a, b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAX=10**6+1\n",
    "primet=[True for i in range(MAX)]\n",
    "prime=[]\n",
    "isinit=False\n",
    "def init():\n",
    "    for i in range(2,MAX):\n",
    "        if primet[i]:\n",
    "            k=i\n",
    "            while k+i<MAX:\n",
    "                k+=i\n",
    "                primet[k]=False\n",
    "    for i in range(2,MAX):\n",
    "        if primet[i]:\n",
    "            prime.append(i)\n",
    "    \n",
    "                \n",
    "            \n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        global isinit\n",
    "        if not isinit:\n",
    "            isinit=True\n",
    "            init()\n",
    "            \n",
    "        s=bisect_left(prime,left)\n",
    "        e=bisect_right(prime,right)\n",
    "        \n",
    "        curans=[-1,-1]\n",
    "        cur=inf\n",
    "        for i in range(s,e):\n",
    "            if i+1<e and prime[i+1]-prime[i]<cur:\n",
    "                cur=prime[i+1]-prime[i]\n",
    "                curans=[prime[i],prime[i+1]]\n",
    "        return curans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:        \n",
    "        N = 10 ** 6 + 1\n",
    "        is_prime = [True] * N\n",
    "        primes = []\n",
    "        for i in range(2, N):\n",
    "            if is_prime[i]:\n",
    "                primes.append(i)\n",
    "                for j in range(i * i, N, i):\n",
    "                    is_prime[j] = False\n",
    "        i = bisect_left(primes, left)\n",
    "        ans = []\n",
    "        min_diff = inf\n",
    "        for k in range(i + 1, len(primes)):\n",
    "            if primes[k] > right:\n",
    "                break\n",
    "            if (d := primes[k] - primes[k - 1]) < min_diff:\n",
    "                min_diff = d\n",
    "                ans = [primes[k - 1], primes[k]]\n",
    "        return [-1, -1] if not ans else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "    # def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "    #     ans = []\n",
    "    #     for i in range(left + 1, right + 1):\n",
    "\n",
    "    #         if self.helper(i) != -1:\n",
    "    #             value = self.helper(i)\n",
    "    #             ans.append(value)\n",
    "    #         if len(ans) == 2:\n",
    "    #             return ans\n",
    "    #     return [-1,-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    # def helper(self, num):\n",
    "    #     for i in range(2, num):\n",
    "    #         if num % i == 0:\n",
    "    #             return -1\n",
    "    #     return num\n",
    "N = 10 ** 6\n",
    "primes = []\n",
    "mark = [True for _ in range(N + 1)]\n",
    "for x in range(2, 10 ** 6 + 1):\n",
    "    if mark[x] == True:\n",
    "        primes.append(x)\n",
    "    for j in range(len(primes)):\n",
    "        if x * primes[j] > N:\n",
    "            break\n",
    "        mark[x * primes[j]] = False\n",
    "        if x % primes[j] == 0:\n",
    "            break\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        i = bisect.bisect_left(primes, left)\n",
    "        nums = []\n",
    "        while i < len(primes):\n",
    "            if primes[i] > right:\n",
    "                break\n",
    "            nums.append(primes[i])\n",
    "            i += 1\n",
    "        \n",
    "        if len(nums) < 2:\n",
    "            return [-1, -1]\n",
    "        \n",
    "        diff = float('inf')\n",
    "        res = [-1, -1]\n",
    "        for i in range(len(nums) - 1):\n",
    "            a = nums[i]\n",
    "            b = nums[i + 1]\n",
    "            if b - a < diff:\n",
    "                diff = b - a\n",
    "                res = [a, b]\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n = 10 ** 6 + 1\n",
    "is_prime = [True] * n\n",
    "primes = []\n",
    "for i in range(2, n):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, n, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        i = bisect_left(primes, left)\n",
    "        j = bisect_right(primes, right)\n",
    "        ans = [-1, -1]\n",
    "        mn = inf\n",
    "        for k in range(i + 1, j):\n",
    "            x = primes[k] - primes[k-1]\n",
    "            # if x <= 2: return [primes[k-1], primes[k]]\n",
    "            if x < mn:\n",
    "                mn = x\n",
    "                ans = [primes[k-1], primes[k]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 6 + 1\n",
    "primes = []\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "primes.extend((MX, MX))  # 保证下面下标不会越界\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        p = q = -1\n",
    "        i = bisect_left(primes, left)\n",
    "        while primes[i + 1] <= right:\n",
    "            if p < 0 or primes[i + 1] - primes[i] < q - p:\n",
    "                p, q = primes[i], primes[i + 1]\n",
    "            i += 1\n",
    "        return [p, q]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        isPrime = [1 for _ in range(0, right+1)]\n",
    "        primeList = []\n",
    "\n",
    "        # for i in range(2, int(left**0.5)+1):\n",
    "        #     if left % i == 0:\n",
    "        #         isPrime[left] = 0\n",
    "\n",
    "        for i in range(2, right+1):\n",
    "            if isPrime[i]:\n",
    "                if i >= left:\n",
    "                    primeList.append(i)\n",
    "                for j in range(i**2, right+1, i):\n",
    "                    isPrime[j] = 0\n",
    "        \n",
    "        min = float('inf')\n",
    "        index = -1\n",
    "        for i in range(0, len(primeList)-1):\n",
    "            if min > primeList[i+1] - primeList[i]:\n",
    "                # print('min=', min, \" pri[i+1]=\", primeList[i+1])\n",
    "                min = primeList[i+1] - primeList[i]\n",
    "                index = i\n",
    "\n",
    "        if index == -1:\n",
    "            return [-1, -1]\n",
    "        # print('isp=', primeList)\n",
    "        return [primeList[index], primeList[index+1]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**6+1\n",
    "prime = []\n",
    "is_prime = [True]*MX\n",
    "for i in range(2,MX):\n",
    "    if is_prime[i]:\n",
    "        prime.append(i)\n",
    "    for j in range(i*i,MX,i):\n",
    "        is_prime[j]=False\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        res = [x for x in prime if left<=x<=right]\n",
    "        ans = []\n",
    "        for i in range(1,len(res)):\n",
    "            x,y=res[i-1],res[i]\n",
    "            if not ans or y-x<ans[-1]-ans[0]:\n",
    "                ans=[x,y]\n",
    "        return ans if ans else [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = []\n",
    "MX = int(1e6)\n",
    "flag = [False] * (MX + 1)\n",
    "for i in range(2, MX+1):\n",
    "    if flag[i] is False:\n",
    "        primes.append(i)\n",
    "    \n",
    "    for num in primes:\n",
    "        if num * i > MX:\n",
    "            break\n",
    "        flag[num * i] = True\n",
    "\n",
    "        if i % num == 0:\n",
    "            break\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:    \n",
    "        l = 0\n",
    "        r = len(primes) - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "\n",
    "            if primes[mid] < left:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        \n",
    "        L = 0\n",
    "        R = len(primes) - 1\n",
    "        while L < R:\n",
    "            mid = (L + R + 1) // 2\n",
    "\n",
    "            if primes[mid] > right:\n",
    "                R = mid - 1\n",
    "            else:\n",
    "                L = mid\n",
    "        \n",
    "        if L - l >= 1:\n",
    "            tmp = primes[l:L+1]\n",
    "            cand = [tmp[-1]-tmp[0], tmp[0], tmp[-1]]\n",
    "\n",
    "            for i in range(len(tmp)-1):\n",
    "                t = tmp[i+1] - tmp[i]\n",
    "                if t < cand[0]:\n",
    "                    cand = [t, tmp[i], tmp[i+1]]\n",
    "                if cand[0] == 3:\n",
    "                    break\n",
    "            return cand[1:]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        isPrime=[True for _ in range(right)]\n",
    "        isPrime[0]=False \n",
    "        prime=[]\n",
    "        for i in range(2,right+1):\n",
    "            if isPrime[i-1]:prime.append(i)      \n",
    "            for p in prime:\n",
    "                if i*p>right:break\n",
    "                isPrime[i*p-1]=False\n",
    "                if i%p==0:break\n",
    "        ret =[-1,-1]\n",
    "        gap=right \n",
    "        pair=[]\n",
    "        for i in range(left,right+1):\n",
    "            if isPrime[i-1]:\n",
    "                if len(pair)==0:\n",
    "                    pair.append(i)\n",
    "                    continue \n",
    "                elif len(pair)==1:pair.append(i)\n",
    "                else:pair[0],pair[1]=pair[1],i \n",
    "                if pair[1]-pair[0]<gap:\n",
    "                    gap=pair[1]-pair[0]\n",
    "                    ret=pair[:]\n",
    "        return ret \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        check, primes_lst = [0 for _ in range(right + 1)], []\n",
    "        check[0], check[1] = 1, 1\n",
    "        for i in range(2, right + 1):\n",
    "            if check[i] == 0:\n",
    "                primes_lst.append(i)\n",
    "                for j in range(i * i, right + 1, i):\n",
    "                    check[j] = 1\n",
    "        num1, num2, gap = -1, -1, right - left\n",
    "        for i in range(len(primes_lst) - 1):\n",
    "            if primes_lst[i] < left:\n",
    "                continue\n",
    "            if primes_lst[i + 1] - primes_lst[i] < gap or (num1 == -1 and primes_lst[i + 1] - primes_lst[i] == gap):\n",
    "                num1, num2, gap = primes_lst[i], primes_lst[i + 1], primes_lst[i + 1] - primes_lst[i]\n",
    "        return [num1, num2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "prime = [2]\n",
    "n = 10**6\n",
    "isprime = [True] * n\n",
    "for i in range(3, n, 2):\n",
    "    if not isprime[i]:\n",
    "        continue\n",
    "    prime.append(i)\n",
    "    for j in range(i*i, n, i):\n",
    "        isprime[j] = False\n",
    "gap = [j - i for i, j in pairwise(prime)]\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        if right < 3:\n",
    "            return [-1,-1]\n",
    "        l = bisect_left(prime, left)\n",
    "        r = bisect_right(prime, right)\n",
    "        t = gap[l:r-1]\n",
    "        if not t:\n",
    "            return [-1,-1]\n",
    "        mn = min(range(len(t)), key=lambda x: t[x])\n",
    "        return prime[mn+l: l+mn+2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "prime = [2]\n",
    "n = 10**6\n",
    "isprime = [True] * n\n",
    "for i in range(3, n, 2):\n",
    "    if not isprime[i]:\n",
    "        continue\n",
    "    prime.append(i)\n",
    "    for j in range(i*i, n, i):\n",
    "        isprime[j] = False\n",
    "gap = [j - i for i, j in pairwise(prime)]\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        l = bisect_left(prime, left)\n",
    "        r = bisect_right(prime, right)\n",
    "        if r < 1:\n",
    "            return [-1,-1]\n",
    "        t = gap[l:r-1]\n",
    "        if not t:\n",
    "            return [-1,-1]\n",
    "        mn = min(range(len(t)), key=lambda x: t[x])\n",
    "        return prime[mn+l: l+mn+2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        def euler_flag_prime(n):\n",
    "    # 欧拉线性筛素数\n",
    "    # 说明：返回小于等于 n 的所有素数\n",
    "            flag = [False for _ in range(n + 1)]\n",
    "            prime_numbers = []\n",
    "            for num in range(2, n + 1):\n",
    "                if not flag[num]:\n",
    "                    prime_numbers.append(num)\n",
    "                for prime in prime_numbers:\n",
    "                    if num * prime > n:\n",
    "                        break\n",
    "                    flag[num * prime] = True\n",
    "                    if num % prime == 0:  # 这句是最有意思的地方  下面解释\n",
    "                        break\n",
    "            return prime_numbers\n",
    "        res = euler_flag_prime(right)\n",
    "        res = [x for x in res if x>=left]\n",
    "        res = list(set(res))\n",
    "        ans = []\n",
    "        for i in res:\n",
    "            if left <= i <= right:\n",
    "                ans.append(i)\n",
    "        if len(ans) <= 1: return [-1,-1]\n",
    "        ans.sort()\n",
    "        tql = []\n",
    "        for i in range(1, len(ans)):\n",
    "            tql.append(ans[i]-ans[i-1])\n",
    "        return ans[tql.index(min(tql)):tql.index(min(tql))+2]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        # 1指数晒 [1,right]范围\n",
    "        # 2 求出left,right返回内所有秩输\n",
    "        # 3答案一定出现在相邻的质数中,如果只有一个质数,return [-1,-1],否则答案一定存在\n",
    "        prime=[True]*(right+1)\n",
    "        prime[0],prime[1]=False,False\n",
    "        for i in range(2,right+1):\n",
    "            if prime[i]:\n",
    "                for j in range(i*i,right+1,i):\n",
    "                    prime[j]=False\n",
    "        primes=[x for x in range(left,right+1) if prime[x]]\n",
    "        if len(primes)<2:\n",
    "            return [-1,-1]\n",
    "        ans=[primes[0],primes[1]]\n",
    "        min_diff=primes[1]-primes[0]\n",
    "        for x,y in zip(primes,primes[1:]):\n",
    "            if y-x<min_diff:\n",
    "                min_diff=y-x\n",
    "                ans=[x,y]\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**6 + 1\n",
    "path = []\n",
    "on_path = [True] * MX\n",
    "on_path[0] = on_path[1] = False\n",
    "for i in range(2, MX):\n",
    "    if on_path[i]:\n",
    "        path.append(i)\n",
    "        for j in range(i**2, MX, i):\n",
    "            on_path[j] = False\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        ret = [-1, -1]\n",
    "        min_diff = inf\n",
    "        temp = [x for x in range(left, right+1) if on_path[x]]\n",
    "        for num1, num2 in pairwise(temp):\n",
    "            diff = num2 - num1\n",
    "            if diff < min_diff:\n",
    "                min_diff = diff\n",
    "                ret = [num1, num2]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 埃氏筛\n",
    "MX = 10 ** 6 + 1\n",
    "primes = []\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "primes.extend((MX, MX))  # 保证下面下标不会越界\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(left, right + 1):\n",
    "            if is_prime[i] and i != 1: res.append(i)\n",
    "        n = len(res)\n",
    "        if n <= 1: return [-1, -1]\n",
    "        mn = inf\n",
    "        for i in range(1, n):\n",
    "            d = res[i] - res[i - 1]\n",
    "            if d < mn:\n",
    "                mn = d\n",
    "                ans = [res[i - 1], res[i]]\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        import math\n",
    "        is_primes = [True] * (right+1)\n",
    "        is_primes[1] = False\n",
    "        for p in range(2, int(math.sqrt(right))+1):\n",
    "            if is_primes[p]:\n",
    "                for pp in range(p*2, right+1, p):\n",
    "                    is_primes[pp] = False\n",
    "\n",
    "        primes = []\n",
    "        prime_prev = -1\n",
    "        for num in range(left, right+1):\n",
    "            if not is_primes[num]:\n",
    "                continue\n",
    "            if len(primes) == 0 or len(primes) == 1:\n",
    "                primes.append(num)\n",
    "            else:\n",
    "                if num - prime_prev < primes[1] - primes[0]:\n",
    "                    primes[0], primes[1] = prime_prev, num\n",
    "            prime_prev = num\n",
    "        if len(primes) < 2:\n",
    "            return [-1, -1]\n",
    "        else:\n",
    "            return primes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        isPrime = [1] * (right + 1)\n",
    "        isPrime[1] = 0\n",
    "        primes = []\n",
    "        for i in range(2, right + 1):\n",
    "            if isPrime[i] == 0:\n",
    "                continue\n",
    "            if i >= left:\n",
    "                primes.append(i)\n",
    "            for j in range(i + i, right + 1, i):\n",
    "                isPrime[j] = 0\n",
    "        \n",
    "        if len(primes) <= 1:\n",
    "            return [-1, -1]\n",
    "        min_ = primes[1] - primes[0]\n",
    "        res = [primes[0], primes[1]]\n",
    "        for i in range(len(primes) - 1):\n",
    "            if primes[i + 1] - primes[i] < min_:\n",
    "                res = [primes[i], primes[i + 1]]\n",
    "                min_ = primes[i + 1] - primes[i]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 线性筛\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        is_prime = [1] * (right+1)\n",
    "        primes = []\n",
    "        \n",
    "        for i in range(2, right+1):\n",
    "            if is_prime[i]:\n",
    "                primes.append(i)\n",
    "                    \n",
    "            for p in primes:\n",
    "                if p * i > right:\n",
    "                    break\n",
    "                is_prime[p*i] = 0\n",
    "                if i % p == 0:\n",
    "                    break\n",
    "        p, q = -1, -1\n",
    "        MX = float('inf')\n",
    "        primes.extend((MX, MX))  # 保证下面下标不会越界\n",
    "        i = bisect.bisect_left(primes, left)  # primes[0..i) < left\n",
    "        while primes[i+1] <= right:\n",
    "            if p < 0 or primes[i+1] - primes[i] < q-p:\n",
    "                p, q = primes[i], primes[i+1]\n",
    "            i += 1\n",
    "        return [p,q]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        def isPrime(Upbound:int) -> list[int]:\n",
    "            lis = [1] * (Upbound+1)\n",
    "            ans=[]\n",
    "            for i in range(2,int(Upbound**(1/2))+1):\n",
    "                if lis[i] == 1:\n",
    "                    ans.append(i)\n",
    "                    tempi = i\n",
    "                    while tempi+i <= Upbound:\n",
    "                        lis[tempi+i] = 0\n",
    "                        tempi += i\n",
    "                pass\n",
    "            for i in range(int(Upbound ** (1 / 2)) + 1, Upbound+ 1):\n",
    "                if lis[i] == 1:\n",
    "                    ans.append(i)\n",
    "\n",
    "            return ans\n",
    "        lis = isPrime(right)\n",
    "        for i in range(len(lis)):\n",
    "            if lis[i]>=left:\n",
    "                lis = lis[i:]\n",
    "                break\n",
    "            if i == len(lis)-1:\n",
    "                lis=[]\n",
    "\n",
    "        if len(lis) <= 1:\n",
    "            return [-1,-1]\n",
    "        else:\n",
    "            ans , ansmin = [lis[0],lis[1]] , lis[1]-lis[0]\n",
    "            for i in range(1,len(lis)-1):\n",
    "                if lis[i+1] - lis[i] < ansmin:\n",
    "                    ansmin = lis[i+1] - lis[i]\n",
    "                    ans = [lis[i],lis[i+1]]\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def prime_table(upper):\n",
    "    n = upper + 1\n",
    "    is_prim = [True] * n\n",
    "    ans = deque()\n",
    "    i = 2\n",
    "    while i * i < n:\n",
    "        if is_prim[i]:\n",
    "            for j in range(i*i, n, i):\n",
    "                is_prim[j] = False\n",
    "        i += 1\n",
    "    for i in range(2, n):\n",
    "        if is_prim[i]:\n",
    "            ans.append(i)\n",
    "    return list(ans)\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        Z = prime_table(right)\n",
    "        ans = [-1, 2**33]\n",
    "        i = len(Z) - 1 - 1\n",
    "        while i >= 0 and Z[i] >= left:\n",
    "            if Z[i+1] - Z[i] <= ans[1] - ans[0]:\n",
    "                ans = Z[i], Z[i+1]\n",
    "            i -= 1\n",
    "        if ans[0] == -1:\n",
    "            ans[1] = -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        # 快慢指针 , 初始位置 l = r = index(first prime)\n",
    "        # 右指针不断的往后寻找下一个质数\n",
    "        # 但是朴素的素数判断时间复杂度是O(logn)的 x\n",
    "        # 使用素数筛法\n",
    "        N = right + 1\n",
    "        isPrime = [True] * (right + 1)    \n",
    "    \n",
    "        def sieve():\n",
    "            isPrime[1] = False\n",
    "            for i in range(2 , N):\n",
    "                if not isPrime[i]:\n",
    "                    continue\n",
    "                for j in range(2 * i, N,  i):\n",
    "                    isPrime[j] = False\n",
    "        sieve()\n",
    "        \n",
    "\n",
    "        l = left\n",
    "        while l < right and isPrime[l] == False:   l += 1\n",
    "        if l >= right:  return [-1 , -1]\n",
    "        r  , m = l + 1, inf\n",
    "        res = [-1 , -1]\n",
    "        while r <= right:\n",
    "            if isPrime[r]:                \n",
    "                if r - l + 1  < m:\n",
    "                    res = [l , r]\n",
    "                    m = r - l + 1\n",
    "                l = r\n",
    "            r += 1\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#预处理,筛质数\n",
    "isprime=[True]*10**6\n",
    "prime=set()\n",
    "for i in range(2,10**6):\n",
    "    if isprime[i]:\n",
    "        prime.add(i)\n",
    "        for j in range(2*i,10**6,i):\n",
    "            isprime[j]=False\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        ans=[]\n",
    "        for num in range(left,right+1):\n",
    "            if num in prime:\n",
    "                ans.append(num)\n",
    "        if len(ans)<2:\n",
    "            return [-1,-1]\n",
    "        d=ans[1]-ans[0]\n",
    "        res=[ans[0],ans[1]]\n",
    "        for i in range(2,len(ans)):\n",
    "            if ans[i]-ans[i-1]<d:\n",
    "                d=ans[i]-ans[i-1]\n",
    "                res[0],res[1]=ans[i-1],ans[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        isPrime = [1]*2000000\n",
    "        isPrime[1] = 0\n",
    "        former = left\n",
    "        num1 = left\n",
    "        num2 = right\n",
    "        for i in range(2,int(right*1.2)):\n",
    "            if isPrime[i] == 1 :\n",
    "                for j in range(2,(right)//i+1):\n",
    "                    isPrime[j*i] = 0\n",
    "                    # print(\"i,j,i*j\",i,j,i*j)\n",
    "                if right >= i >= left :\n",
    "                    # print('i:',i)\n",
    "                    # if i == 13:\n",
    "                        # print('**',i,isPrime[i])\n",
    "                    if isPrime[num1] == 0:\n",
    "                        # print(\"i:\",i,'num1',num1)\n",
    "                        num1 = i\n",
    "                        former = i\n",
    "                    # print('former,i',former,i,num1,num2)\n",
    "                    if 0 < i-former < num2 - num1:\n",
    "                        num2 = i\n",
    "                        num1 = former    \n",
    "                    former = i\n",
    "                    \n",
    "        if isPrime[num1] == 0 or isPrime[num2] == 0:\n",
    "            return [-1,-1]\n",
    "        if num1 == num2 :\n",
    "            return [-1,-1]\n",
    "        return [num1,num2]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        isprime = [1]*(right+1)\n",
    "        isprime[0] = isprime[1] = 0\n",
    "        for i in range(2,int(right**0.5)+1):\n",
    "            if isprime[i]:\n",
    "                isprime[i*i:right+1:i] = [0]*len(isprime[i*i:right+1:i])\n",
    "        ans = [-1,-1]\n",
    "        pre = -inf\n",
    "        cnt = inf\n",
    "        for i in range(left,right+1):\n",
    "            if isprime[i]:\n",
    "                tmp = i-pre\n",
    "                if tmp<cnt:\n",
    "                    cnt = tmp\n",
    "                    ans = [pre,i]\n",
    "                pre = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        n = right + 1\n",
    "        prm = [True] * n\n",
    "        p = []\n",
    "        for i in range(2, n):\n",
    "            if prm[i]:\n",
    "                p.append(i)   \n",
    "            for j in p:\n",
    "                tmp = i * j\n",
    "                if tmp >= n:\n",
    "                    break\n",
    "                prm[tmp] = False\n",
    "                if i % j == 0:\n",
    "                    break\n",
    "        p = [i for i in range(2, n) if i >= left and prm[i]]\n",
    "        if len(p) < 2:\n",
    "            return [-1, -1]\n",
    "        idx = 1\n",
    "        for i in range(1, len(p)):\n",
    "            if p[i] - p[i - 1] < p[idx] - p[idx - 1]:\n",
    "                idx = i\n",
    "        return [p[idx - 1], p[idx]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        #判断质数，滑窗锁口\n",
    "        zl = [1]*(right+1)\n",
    "        ind = 0\n",
    "        zl[0] = zl[1] = 0\n",
    "        \n",
    "        \n",
    "        for i in range(2,int((right+1)**0.5 +1)):\n",
    "            if zl[i]:\n",
    "                zl[i * i: right+1 : i] = [0] * ((right  - i * i) // i + 1)\n",
    "        # print(zl)\n",
    "        \n",
    "        \n",
    "        \n",
    "        zl = zl[left:right+1]\n",
    "        # print(zl)\n",
    "        res = len(zl)\n",
    "        if sum(zl)<2:\n",
    "            return [-1,-1]\n",
    "        \n",
    "        \n",
    "        # print(zl)\n",
    "        \n",
    "        app = -1\n",
    "        for i in range(len(zl)):\n",
    "            if zl[i]==1:\n",
    "                if app>-1 and i-app<res:\n",
    "                    res = i-app\n",
    "                    ans = [app,i]\n",
    "                app = i\n",
    "                \n",
    "        return [left+ans[0],left+ans[1]]\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        prime = []\n",
    "        p = [True] * (right + 1)\n",
    "        for i in range(2, right + 1):\n",
    "            if p[i]:\n",
    "                if i >= left:\n",
    "                    prime.append(i)\n",
    "                for j in range(i * i, right + 1, i):\n",
    "                    p[j] = False\n",
    "        mn = right\n",
    "        ans = [-1, -1]\n",
    "        for i in range(1, len(prime)):\n",
    "            if prime[i] - prime[i - 1] < mn:\n",
    "                mn = prime[i] - prime[i - 1]\n",
    "                ans = [prime[i - 1], prime[i]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        # 埃筛法\n",
    "        MX = right + 1\n",
    "        primes = []\n",
    "        is_prime = [True] * MX\n",
    "        for i in range(2, MX):\n",
    "            if is_prime[i]:\n",
    "                if i >= left:\n",
    "                    primes.append(i)\n",
    "                for j in range(i * i, MX, i):\n",
    "                    is_prime[j] = False\n",
    "        # print(primes)\n",
    "        cur = d = inf\n",
    "        for i in range(1, len(primes)):\n",
    "            if primes[i] - primes[i - 1] < d:\n",
    "                cur = i - 1\n",
    "                d = primes[i] - primes[i - 1]\n",
    "        if cur == inf:\n",
    "            return [-1, -1]\n",
    "        return [primes[cur], primes[cur + 1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n = 10 ** 6\n",
    "d = [0] * (n + 1)\n",
    "p = [0] * (n + 1)\n",
    "idx = 0\n",
    "\n",
    "i = 2\n",
    "while i <= n:\n",
    "    if d[i] == 0:\n",
    "        p[idx] = i\n",
    "        idx += 1\n",
    "    j = 0\n",
    "    while p[j] <= n / i:\n",
    "        d[p[j] * i] = 1\n",
    "        if i % p[j] == 0: break\n",
    "        j += 1\n",
    "    i += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        prev = None\n",
    "        ans = [-1, -1]\n",
    "        d = inf\n",
    "        for i in range(idx):\n",
    "            if p[i] > right: break\n",
    "            if p[i] >= left and p[i] <= right:\n",
    "                if prev:\n",
    "                    curd = p[i] - prev\n",
    "                    if curd < d:\n",
    "                        ans = [prev, p[i]]\n",
    "                        d = curd\n",
    "                prev = p[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        n = right+1\n",
    "        cnt = []\n",
    "        used = [0]*n\n",
    "        for i in range(2,n):\n",
    "            if not used[i]:\n",
    "                cnt.append(i)\n",
    "                used[i:n:i] = [1]*((n-1)//i)\n",
    "        res,ans = [-1,-1],float('inf')\n",
    "        for i in range(1,len(cnt)):\n",
    "            if cnt[i-1] < left:continue\n",
    "            if cnt[i]-cnt[i-1] < ans:\n",
    "                ans = cnt[i]-cnt[i-1]\n",
    "                res = [cnt[i-1],cnt[i]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000010\n",
    "st,prime = [False]*N,[0]*N\n",
    "class Solution:\n",
    "    def closestPrimes(self, l: int, r: int) -> List[int]:\n",
    "        if r <= 2:\n",
    "            return [-1,-1]\n",
    "        x = r\n",
    "        cnt = 0\n",
    "        for i in range(2,r+1):\n",
    "            if not st[i]:\n",
    "                prime[cnt] = i\n",
    "                cnt += 1\n",
    "            j = 0\n",
    "            while prime[j] <= x//i:\n",
    "                st[prime[j]*i] = True\n",
    "                if(i%prime[j] == 0):\n",
    "                    break\n",
    "                j += 1\n",
    "        ans = []\n",
    "        for i in prime:\n",
    "            if i >= l and i <= r:\n",
    "                ans.append(i)\n",
    "        if len(ans) <= 1:\n",
    "            return [-1,-1]\n",
    "        i1,i2 = ans[0],ans[1]\n",
    "        for i in range(1,len(ans)):\n",
    "            if ans[i]-ans[i-1] < i2-i1:\n",
    "                i1,i2 = ans[i-1],ans[i]\n",
    "        return [i1,i2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 艾式筛\n",
    "    def closestPrimes(self, left: int, right: int) -> List[int]:\n",
    "        is_prime = [1] * (right+1)\n",
    "        primes = []\n",
    "        minDiff = float('inf')\n",
    "        res = [-1,-1]\n",
    "        for i in range(2, right+1):\n",
    "            if is_prime[i]:\n",
    "                if i >= left:\n",
    "                    primes.append(i)\n",
    "                if len(primes) >= 2 and primes[-1] - primes[-2] < minDiff:\n",
    "                    minDiff = primes[-1] - primes[-2]\n",
    "                    res = [primes[-2], primes[-1]]\n",
    "                    \n",
    "                for j in range(i*i, right + 1, i):\n",
    "                    is_prime[j] = 0\n",
    "\n",
    "        # print(primes)\n",
    "        return res "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
